package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * 2139. 得到目标值的最少行动次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/9 15:36
 */
public class MinMoves {

    public static void main(String[] args) {
        MinMoves test = new MinMoves();

        // 7
//        int a = 19;
//        int b = 2;

        // 4
//        int a = 10;
//        int b = 4;

        // 4
//        int a = 5;
//        int b = 0;

        // 85234
        int a = 5454656;
        int b = 6;

        int i = test.minMoves(a, b);
        System.out.println(i);
    }

    public int minMoves(int target, int maxDoubles) {
        if (target < 4 || maxDoubles == 0) {
            return target - 1;
        }
        String s = Integer.toBinaryString(target);
        int length = s.length();
        if (length - 2 <= maxDoubles) {
            return length - 2 + Integer.bitCount(target);
        }
        int c = 0;
        for (int i = 0; i < maxDoubles; i++) {
            c = (c << 1) + 1;
        }
        return (target >> maxDoubles) - 1 + maxDoubles + Integer.bitCount(target & c);
    }
}
